package com.zzz.dynamic.cutrod;

public class CutRod {

    public static int count = 0;
    public static int[] rodPrice = new int[]{0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    public static int[] maxPriceArray = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    public static void main(String[] args) {
        // 协议个方法，参数是一个长度n  返回切割得到分段钢材加起来的最大价值
        // 分析，其实很好理解，就是得把所有情况都给算一遍，然后选择最大的那个，但是要去除这其中的重复计算，比穷举法会优化点
        // 因为动态规划涉及到的是子问题。所有子问题中必然会出现子问题重合情况

        System.out.println(getMaxCut4(4));

        System.out.println("方法调用次数" + count);

    }

    // 版本1 只是用递归 只求实现，不优化重复计算问题
    // 长度为10 方法调用了19683 次
    public static int getMaxCut(int n) {
        count++;
        // 如果长度为0 ，那么直接返回价值0
        if (n == 0) {
            return rodPrice[0];
        }

        // 该长度如果不切割的价值为rodPrice[n]
        int maxPrice = rodPrice[n];

        // 遍历切割的方式，有n-1种，按切割断点来看不考虑长度重复情况
        // 1 n-1 / 2 n-2 / 3 n-3 ....  n>3的时候
        for (int i = 1; i < (n / 2 + 1); i++) {
            // 计算出切割后各自的最大价值，加起来和当前最大价值比较，去较大的那个，因为计算长度为n的最大切割价值完全处理方式一致的子问题。
            // 因此使用递归求解，档切割到1的时候其实就是取本身，切割到2还能1 1切割
            maxPrice = Math.max(maxPrice, getMaxCut(i) + getMaxCut(n - i));
        }
        return maxPrice;
    }

    public static int getMaxCut2(int n) {
        count++;
        // 如果长度为0 ，那么直接返回价值0
        if (n == 0) {
            return rodPrice[0];
        }

        if (maxPriceArray[n] > 0) {
            return maxPriceArray[n];
        }

        // 该长度如果不切割的价值为rodPrice[n]
        int maxPrice = rodPrice[n];

        // 遍历切割的方式，有n-1种，按切割断点来看不考虑长度重复情况
        // 1 n-1 / 2 n-2 / 3 n-3 ....  n>3的时候
        for (int i = 1; i < (n / 2 + 1); i++) {
            // 计算出切割后各自的最大价值，加起来和当前最大价值比较，去较大的那个，因为计算长度为n的最大切割价值完全处理方式一致的子问题。
            // 因此使用递归求解，档切割到1的时候其实就是取本身，切割到2还能1 1切割
            maxPrice = Math.max(maxPrice, getMaxCut2(i) + getMaxCut2(n - i));
        }
        maxPriceArray[n] = maxPrice;
        return maxPrice;
    }

    // 继续优化，分割方式 从两段两段分割，换一个角度，一段固定，另一端进行子问题求解，  这个思路是否可行
    // 该思路 与 原分割 得到的效果一致的理由：
    // 虽然吧一端固定，另一端进行分割求解，但是同样能够覆盖所有情况
    public static int getMaxCut3(int n) {
        count++;
        if (n == 0) {
            return rodPrice[0];
        }
        if(maxPriceArray[n] > 0) {
            return maxPriceArray[n];
        }
        int maxPrice = rodPrice[n];
        for (int i = 1; i < n; i++) {
            maxPrice = Math.max(maxPrice, rodPrice[i] + getMaxCut3(n - i));
        }
        maxPriceArray[n] = maxPrice;
        return maxPrice;
    }

    // 自底向上求解
    public static int getMaxCut4(int n) {
        count++;
        for(int i = 1; i <= n; i++) {
            int maxPrice = rodPrice[i];
            for(int j=1; j<=i; j++) {
                maxPrice = Math.max(maxPrice, rodPrice[j] + maxPriceArray[i-j]);
            }
            maxPriceArray[i] = maxPrice;
        }
        return maxPriceArray[n];
    }


    // 总结，动态规划

}
